Node / ReticulumProjects / Reticulum.git / files / RNS / Cryptography / X25519.py

Displaying Raw • Download

T8b949e# By Nicko van Someren, 2021. This code is released into the public domain.

T8b949e# Small modifications for use in Reticulum, and constant time key exchange

T8b949e# added by Mark Qvist in 2022.

T8b949e# WARNING! Only the X25519PrivateKey.exchange() method attempts to hide execution time.

T8b949e# In the context of Reticulum, this is sufficient, but it may not be in other systems. If

T8b949e# this code is to be used to provide cryptographic security in an environment where the

T8b949e# start and end times of the execution can be guessed, inferred or measured then it is

T8b949e# critical that steps are taken to hide the execution time, for instance by adding a

T8b949e# delay so that encrypted packets are not sent until a fixed time after the _start_ of

T8b949e# execution.

Tff7b72import T7ee787os

Tff7b72import T7ee787time

Te6edf3P Tff7b72= T79c0ff2 Tff7b72*Tff7b72* T79c0ff255 Tff7b72- T79c0ff19

Te6edf3_A Tff7b72= T79c0ff486662

Tff7b72def Td2a8ff_point_addTb4b4b4(Te6edf3point_nTb4b4b4, Te6edf3point_mTb4b4b4, Te6edf3point_diffTb4b4b4)Tb4b4b4:

T8b949e"""Given the projection of two points and their difference, return their sum"""

Tb4b4b4(Te6edf3xnTb4b4b4, Te6edf3znTb4b4b4) Tff7b72= Te6edf3point_n

Tb4b4b4(Te6edf3xmTb4b4b4, Te6edf3zmTb4b4b4) Tff7b72= Te6edf3point_m

Tb4b4b4(Te6edf3x_diffTb4b4b4, Te6edf3z_diffTb4b4b4) Tff7b72= Te6edf3point_diff

Te6edf3x Tff7b72= Tb4b4b4(Te6edf3z_diff Tff7b72<< T79c0ff2Tb4b4b4) Tff7b72* Tb4b4b4(Te6edf3xm Tff7b72* Te6edf3xn Tff7b72- Te6edf3zm Tff7b72* Te6edf3znTb4b4b4) Tff7b72*Tff7b72* T79c0ff2

Te6edf3z Tff7b72= Tb4b4b4(Te6edf3x_diff Tff7b72<< T79c0ff2Tb4b4b4) Tff7b72* Tb4b4b4(Te6edf3xm Tff7b72* Te6edf3zn Tff7b72- Te6edf3zm Tff7b72* Te6edf3xnTb4b4b4) Tff7b72*Tff7b72* T79c0ff2

Tff7b72return Te6edf3x Tff7b72% Te6edf3PTb4b4b4, Te6edf3z Tff7b72% Te6edf3P

Tff7b72def Td2a8ff_point_doubleTb4b4b4(Te6edf3point_nTb4b4b4)Tb4b4b4:

T8b949e"""Double a point provided in projective coordinates"""

Tb4b4b4(Te6edf3xnTb4b4b4, Te6edf3znTb4b4b4) Tff7b72= Te6edf3point_n

Te6edf3xn2 Tff7b72= Te6edf3xn Tff7b72*Tff7b72* T79c0ff2

Te6edf3zn2 Tff7b72= Te6edf3zn Tff7b72*Tff7b72* T79c0ff2

Te6edf3x Tff7b72= Tb4b4b4(Te6edf3xn2 Tff7b72- Te6edf3zn2Tb4b4b4) Tff7b72*Tff7b72* T79c0ff2

Te6edf3xzn Tff7b72= Te6edf3xn Tff7b72* Te6edf3zn

Te6edf3z Tff7b72= T79c0ff4 Tff7b72* Te6edf3xzn Tff7b72* Tb4b4b4(Te6edf3xn2 Tff7b72+ Te6edf3_A Tff7b72* Te6edf3xzn Tff7b72+ Te6edf3zn2Tb4b4b4)

Tff7b72return Te6edf3x Tff7b72% Te6edf3PTb4b4b4, Te6edf3z Tff7b72% Te6edf3P

Tff7b72def Td2a8ff_const_time_swapTb4b4b4(Te6edf3aTb4b4b4, Te6edf3bTb4b4b4, Te6edf3swapTb4b4b4)Tb4b4b4:

T8b949e"""Swap two values in constant time"""

Te6edf3index Tff7b72= Tffa657intTb4b4b4(Te6edf3swapTb4b4b4) Tff7b72* T79c0ff2

Te6edf3temp Tff7b72= Tb4b4b4(Te6edf3aTb4b4b4, Te6edf3bTb4b4b4, Te6edf3bTb4b4b4, Te6edf3aTb4b4b4)

Tff7b72return Te6edf3tempTb4b4b4[Te6edf3indexTb4b4b4:Te6edf3indexTff7b72+T79c0ff2Tb4b4b4]

Tff7b72def Td2a8ff_raw_curve25519Tb4b4b4(Te6edf3baseTb4b4b4, Te6edf3nTb4b4b4)Tb4b4b4:

T8b949e"""Raise the point base to the power n"""

Te6edf3zero Tff7b72= Tb4b4b4(T79c0ff1Tb4b4b4, T79c0ff0Tb4b4b4)

Te6edf3one Tff7b72= Tb4b4b4(Te6edf3baseTb4b4b4, T79c0ff1Tb4b4b4)

Te6edf3mPTb4b4b4, Te6edf3m1P Tff7b72= Te6edf3zeroTb4b4b4, Te6edf3one

Tff7b72for Te6edf3i Tff7b72in Tffa657reversedTb4b4b4(Tffa657rangeTb4b4b4(T79c0ff256Tb4b4b4)Tb4b4b4)Tb4b4b4:

Te6edf3bit Tff7b72= Tffa657boolTb4b4b4(Te6edf3n Tff7b72& Tb4b4b4(T79c0ff1 Tff7b72<< Te6edf3iTb4b4b4)Tb4b4b4)

Te6edf3mPTb4b4b4, Te6edf3m1P Tff7b72= Te6edf3_const_time_swapTb4b4b4(Te6edf3mPTb4b4b4, Te6edf3m1PTb4b4b4, Te6edf3bitTb4b4b4)

Te6edf3mPTb4b4b4, Te6edf3m1P Tff7b72= Te6edf3_point_doubleTb4b4b4(Te6edf3mPTb4b4b4)Tb4b4b4, Te6edf3_point_addTb4b4b4(Te6edf3mPTb4b4b4, Te6edf3m1PTb4b4b4, Te6edf3oneTb4b4b4)

Te6edf3mPTb4b4b4, Te6edf3m1P Tff7b72= Te6edf3_const_time_swapTb4b4b4(Te6edf3mPTb4b4b4, Te6edf3m1PTb4b4b4, Te6edf3bitTb4b4b4)

Te6edf3xTb4b4b4, Te6edf3z Tff7b72= Te6edf3mP

Te6edf3inv_z Tff7b72= Tffa657powTb4b4b4(Te6edf3zTb4b4b4, Te6edf3P Tff7b72- T79c0ff2Tb4b4b4, Te6edf3PTb4b4b4)

Tff7b72return Tb4b4b4(Te6edf3x Tff7b72* Te6edf3inv_zTb4b4b4) Tff7b72% Te6edf3P

Tff7b72def Td2a8ff_unpack_numberTb4b4b4(Te6edf3sTb4b4b4)Tb4b4b4:

T8b949e"""Unpack 32 bytes to a 256 bit value"""

Tff7b72if Tffa657lenTb4b4b4(Te6edf3sTb4b4b4) Tff7b72!= T79c0ff32Tb4b4b4:

Tff7b72raise Tf85149ValueErrorTb4b4b4(Ta5d6ff'Ta5d6ffCurve25519 values must be 32 bytesTa5d6ff'Tb4b4b4)

Tff7b72return Tffa657intTff7b72.Td2a8fffrom_bytesTb4b4b4(Te6edf3sTb4b4b4, Ta5d6ff"Ta5d6fflittleTa5d6ff"Tb4b4b4)

Tff7b72def Td2a8ff_pack_numberTb4b4b4(Te6edf3nTb4b4b4)Tb4b4b4:

T8b949e"""Pack a value into 32 bytes"""

Tff7b72return Te6edf3nTff7b72.Td2a8ffto_bytesTb4b4b4(T79c0ff32Tb4b4b4, Ta5d6ff"Ta5d6fflittleTa5d6ff"Tb4b4b4)

Tff7b72def Td2a8ff_fix_secretTb4b4b4(Te6edf3nTb4b4b4)Tb4b4b4:

T8b949e"""Mask a value to be an acceptable exponent"""

Te6edf3n Tff7b72&Tff7b72= Tff7b72~T79c0ff7

Te6edf3n Tff7b72&Tff7b72= Tff7b72~Tb4b4b4(T79c0ff128 Tff7b72<< T79c0ff8 Tff7b72* T79c0ff31Tb4b4b4)

Te6edf3n Tff7b72|Tff7b72= T79c0ff64 Tff7b72<< T79c0ff8 Tff7b72* T79c0ff31

Tff7b72return Te6edf3n

Tff7b72def Td2a8ff_fix_base_pointTb4b4b4(Te6edf3nTb4b4b4)Tb4b4b4:

Te6edf3n Tff7b72&Tff7b72= Tff7b72~Tb4b4b4(T79c0ff2Tff7b72*Tff7b72*T79c0ff255Tb4b4b4)

Tff7b72return Te6edf3n

Tff7b72def Td2a8ffcurve25519Tb4b4b4(Te6edf3base_point_rawTb4b4b4, Te6edf3secret_rawTb4b4b4)Tb4b4b4:

T8b949e"""Raise the base point to a given power"""

Te6edf3base_point Tff7b72= Te6edf3_fix_base_pointTb4b4b4(Te6edf3_unpack_numberTb4b4b4(Te6edf3base_point_rawTb4b4b4)Tb4b4b4)

Te6edf3secret Tff7b72= Te6edf3_fix_secretTb4b4b4(Te6edf3_unpack_numberTb4b4b4(Te6edf3secret_rawTb4b4b4)Tb4b4b4)

Tff7b72return Te6edf3_pack_numberTb4b4b4(Te6edf3_raw_curve25519Tb4b4b4(Te6edf3base_pointTb4b4b4, Te6edf3secretTb4b4b4)Tb4b4b4)

Tff7b72def Td2a8ffcurve25519_baseTb4b4b4(Te6edf3secret_rawTb4b4b4)Tb4b4b4:

T8b949e"""Raise the generator point to a given power"""

Te6edf3secret Tff7b72= Te6edf3_fix_secretTb4b4b4(Te6edf3_unpack_numberTb4b4b4(Te6edf3secret_rawTb4b4b4)Tb4b4b4)

Tff7b72return Te6edf3_pack_numberTb4b4b4(Te6edf3_raw_curve25519Tb4b4b4(T79c0ff9Tb4b4b4, Te6edf3secretTb4b4b4)Tb4b4b4)

Tff7b72class T56d364X25519PublicKeyTb4b4b4:

Tff7b72def Tff7b72__init__Tb4b4b4(Tff7b72selfTb4b4b4, Te6edf3xTb4b4b4)Tb4b4b4:

Tff7b72selfTff7b72.Td2a8ffx Tff7b72= Te6edf3x

Tf0883e@classmethod

Tff7b72def Td2a8fffrom_public_bytesTb4b4b4(Tff7b72clsTb4b4b4, Te6edf3dataTb4b4b4)Tb4b4b4:

Tff7b72return Tff7b72clsTb4b4b4(Te6edf3_unpack_numberTb4b4b4(Te6edf3dataTb4b4b4)Tb4b4b4)

Tff7b72def Td2a8ffpublic_bytesTb4b4b4(Tff7b72selfTb4b4b4)Tb4b4b4:

Tff7b72return Te6edf3_pack_numberTb4b4b4(Tff7b72selfTff7b72.Td2a8ffxTb4b4b4)

Tff7b72class T56d364X25519PrivateKeyTb4b4b4:

Te6edf3MIN_EXEC_TIME Tff7b72= T79c0ff0.002

Te6edf3MAX_EXEC_TIME Tff7b72= T79c0ff0.5

Te6edf3DELAY_WINDOW Tff7b72= T79c0ff10

Te6edf3T_CLEAR Tff7b72= Tff7b72None

Te6edf3T_MAX Tff7b72= T79c0ff0

Tff7b72def Tff7b72__init__Tb4b4b4(Tff7b72selfTb4b4b4, Te6edf3aTb4b4b4)Tb4b4b4:

Tff7b72selfTff7b72.Td2a8ffa Tff7b72= Te6edf3a

Tf0883e@classmethod

Tff7b72def Td2a8ffgenerateTb4b4b4(Tff7b72clsTb4b4b4)Tb4b4b4:

Tff7b72return Tff7b72clsTff7b72.Td2a8fffrom_private_bytesTb4b4b4(Te6edf3osTff7b72.Td2a8ffurandomTb4b4b4(T79c0ff32Tb4b4b4)Tb4b4b4)

Tf0883e@classmethod

Tff7b72def Td2a8fffrom_private_bytesTb4b4b4(Tff7b72clsTb4b4b4, Te6edf3dataTb4b4b4)Tb4b4b4:

Tff7b72return Tff7b72clsTb4b4b4(Te6edf3_fix_secretTb4b4b4(Te6edf3_unpack_numberTb4b4b4(Te6edf3dataTb4b4b4)Tb4b4b4)Tb4b4b4)

Tff7b72def Td2a8ffprivate_bytesTb4b4b4(Tff7b72selfTb4b4b4)Tb4b4b4:

Tff7b72return Te6edf3_pack_numberTb4b4b4(Tff7b72selfTff7b72.Td2a8ffaTb4b4b4)

Tff7b72def Td2a8ffpublic_keyTb4b4b4(Tff7b72selfTb4b4b4)Tb4b4b4:

Tff7b72return Te6edf3X25519PublicKeyTff7b72.Td2a8fffrom_public_bytesTb4b4b4(Te6edf3_pack_numberTb4b4b4(Te6edf3_raw_curve25519Tb4b4b4(T79c0ff9Tb4b4b4, Tff7b72selfTff7b72.Td2a8ffaTb4b4b4)Tb4b4b4)Tb4b4b4)

Tff7b72def Td2a8ffexchangeTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3peer_public_keyTb4b4b4)Tb4b4b4:

Tff7b72if Tffa657isinstanceTb4b4b4(Te6edf3peer_public_keyTb4b4b4, Tffa657bytesTb4b4b4)Tb4b4b4:

Te6edf3peer_public_key Tff7b72= Te6edf3X25519PublicKeyTff7b72.Td2a8fffrom_public_bytesTb4b4b4(Te6edf3peer_public_keyTb4b4b4)

Te6edf3start Tff7b72= Te6edf3timeTff7b72.Td2a8fftimeTb4b4b4(Tb4b4b4)

Te6edf3shared Tff7b72= Te6edf3_pack_numberTb4b4b4(Te6edf3_raw_curve25519Tb4b4b4(Te6edf3peer_public_keyTff7b72.Td2a8ffxTb4b4b4, Tff7b72selfTff7b72.Td2a8ffaTb4b4b4)Tb4b4b4)

Te6edf3end Tff7b72= Te6edf3timeTff7b72.Td2a8fftimeTb4b4b4(Tb4b4b4)

Te6edf3duration Tff7b72= Te6edf3endTff7b72-Te6edf3start

Tff7b72if Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_CLEAR Tff7b72== Tff7b72NoneTb4b4b4:

Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_CLEAR Tff7b72= Te6edf3end Tff7b72+ Te6edf3X25519PrivateKeyTff7b72.Td2a8ffDELAY_WINDOW

Tff7b72if Te6edf3end Tff7b72> Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_CLEARTb4b4b4:

Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_CLEAR Tff7b72= Te6edf3end Tff7b72+ Te6edf3X25519PrivateKeyTff7b72.Td2a8ffDELAY_WINDOW

Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_MAX Tff7b72= T79c0ff0

Tff7b72if Te6edf3duration Tff7b72< Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_MAX Tff7b72or Te6edf3duration Tff7b72< Te6edf3X25519PrivateKeyTff7b72.Td2a8ffMIN_EXEC_TIMETb4b4b4:

Te6edf3target Tff7b72= Te6edf3startTff7b72+Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_MAX

Tff7b72if Te6edf3target Tff7b72> Te6edf3startTff7b72+Te6edf3X25519PrivateKeyTff7b72.Td2a8ffMAX_EXEC_TIMETb4b4b4:

Te6edf3target Tff7b72= Te6edf3startTff7b72+Te6edf3X25519PrivateKeyTff7b72.Td2a8ffMAX_EXEC_TIME

Tff7b72if Te6edf3target Tff7b72< Te6edf3startTff7b72+Te6edf3X25519PrivateKeyTff7b72.Td2a8ffMIN_EXEC_TIMETb4b4b4:

Te6edf3target Tff7b72= Te6edf3startTff7b72+Te6edf3X25519PrivateKeyTff7b72.Td2a8ffMIN_EXEC_TIME

Tff7b72tryTb4b4b4:

Te6edf3timeTff7b72.Td2a8ffsleepTb4b4b4(Te6edf3targetTff7b72-Te6edf3timeTff7b72.Td2a8fftimeTb4b4b4(Tb4b4b4)Tb4b4b4)

Tff7b72except Tf85149Exception Tff7b72as Te6edf3eTb4b4b4:

Tff7b72pass

Tff7b72elif Te6edf3duration Tff7b72> Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_MAXTb4b4b4:

Te6edf3X25519PrivateKeyTff7b72.Td2a8ffT_MAX Tff7b72= Te6edf3duration

Tff7b72return Te6edf3shared